package com.backpack;

import java.util.Arrays;

public class PartitionEqualSubsetSum_416 {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if(sum % 2 != 0) return false;

        int tar = sum / 2 ;

        //dp[i][j] 在【0，i】中任取 放在容量为j的包中，产生的最大价值为dp[i][j]
        //dp[j]  滚动数组，表示 容量j的背包中，最大价值为dp[j].

        //dp[i] 表示 容量和为i的集合中，最大的和为dp[i]，
        //如果dp[target] == target 那么返回true
        int[] dp = new int[tar+1];

        //初始化
         for (int i = 0; i < dp.length; i++) {
             if(i >= nums[0] ) dp[i] = nums[0];
         }

        for (int i = 1; i < nums.length; i++) {
            for (int j = dp.length-1; j >=nums[i]; j--) {
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }

        return dp[tar] == tar;

    }
}
